package 爆刷leetcode.day0615;

/**
 * @Author yaya
 * @Create 2024/6/15 9:58
 * Description:最大子数组和
 */
public class Code0053_MaxSubSum {

    /**
     * 使用分治思想递归进行求解
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return maxSubArray(nums, 0, nums.length - 1);
    }

    public int maxSubArray(int[] nums, int left, int right) {

        if (left >= right) {
            return nums[left];
        }

        int mid = left + ((right - left) >> 1);
        int crossSum = getCrossMax(nums, mid, left, right);
        int leftSum = maxSubArray(nums, left, mid);
        int rightSum = maxSubArray(nums, mid + 1, right);
        return Math.max(Math.max(crossSum, leftSum), rightSum);
    }

    public int getCrossMax(int[] nums, int mid, int left, int right) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }

        return leftSum + rightSum;
    }
}
